package Leetcode;

public class problem75 {
    public void sortColors(int[] nums) {
        if(nums == null || nums.length < 2){
            return;
        }

        sort(nums,0,nums.length - 1);

    }

    public void sort(int[] arr , int l ,int r){
        if(l < r){
            int[] p = partition(arr,l,r);
            sort(arr,l,p[0]);
            sort(arr,p[1],r);
        }
    }

    public int[] partition(int[] arr , int l ,int r){
        int index = l - 1;
        int random = (int)Math.random()*(r - l)+l;
        swap(arr,random,r);
        int flag = arr[r];
        int rindex = r;
        while( l < rindex ){
            if(arr[l] < flag){
                swap(arr,++index,l++);
            }else if(arr[l] > flag){
                swap(arr,l,--rindex);
            }else{
                l++;
            }
        }

        swap(arr,r,rindex);
        return new int[]{index,rindex + 1};
    }

    public void swap(int[] arr , int i , int j){
        int temp = arr[i] ;
        arr[i] = arr[j] ;
        arr[j] = temp;
    }
}
